package 二叉树;

public class No98验证二叉搜索树 {

    /**
     * 给定一个二叉树，判断其是否是一个有效的二叉搜索树。
     *
     * 假设一个二叉搜索树具有如下特征：
     *
     * 节点的左子树只包含小于当前节点的数。
     * 节点的右子树只包含大于当前节点的数。
     * 所有左子树和右子树自身必须也是二叉搜索树。
     * 示例 1:
     *
     * 输入:
     *     2
     *    / \
     *   1   3
     * 输出: true
     * 示例 2:
     *
     * 输入:
     *     5
     *    / \
     *   1   4
     *      / \
     *     3   6
     * 输出: false
     * 解释: 输入为: [5,1,4,null,null,3,6]。
     *      根节点的值为 5 ，但是其右子节点值为 4 。
     */

    //一颗节点一颗节点的判断,还是可以有更快捷的方法?
    //自底向上就可以节约很多时间

    /**
     * 很烂的递归...我思路很蠢,本还想去评论区看看有没有自底向上的递归,后来才发现要使用二叉搜索树性质
     */
    public boolean isValidBST(TreeNode root) {
        if(root==null)
            return true;
        boolean dg1 = dg(root, root.left, true);
        boolean dg2 = dg(root, root.right, false);
        if(!dg1)
            return false;
        if(!dg2)
            return false;
        boolean flag1 = isValidBST(root.left);
        boolean flag2 = isValidBST(root.right);
        return flag1&&flag2;
    }

    private boolean dg(TreeNode root,TreeNode node,boolean isLeft){
        if(node==null)
            return true;
        if(isLeft){//左边都要小于父节点
            if(node.val>=root.val)//大了
                return false;
        }else{//反之
            if(node.val<=root.val)
                return false;
        }
        if(node.left!=null) {
            if (node.val <= node.left.val)
                return false;
        }
        if(node.right!=null){
            if(node.val>=node.right.val)
                return false;
        }
        return dg(root,node.left,isLeft)&&dg(root,node.right,isLeft);
    }

    //利用二分搜索树的性质进行递归
    public boolean isValidBSTGood1(TreeNode root){
        //当前节点,左子树最大的就是当前节点,右子树最小的就是当前节点
        return dg1(root,Integer.MIN_VALUE+1,Integer.MAX_VALUE-1);
    }

    private boolean dg1(TreeNode node,long min,long max){
        if (node==null)
            return true;
        if(node.val>=max||node.val<=min)//需要顾虑root.val为maxInteger的情况
            return false;
        boolean flag1 = dg1(node.left, min, node.val);//一直向左时这个min是永远不会变的
        boolean flag2 = dg1(node.right, node.val, max);//max同上
        return flag1&&flag2;
    }

    //利用中序遍历
    public boolean isValidBSTGood2(TreeNode root){
        return dg2(root);
    }

    private long number=Long.MIN_VALUE;

    private boolean dg2(TreeNode node){
        if(node==null)
            return true;
        boolean flag1 = dg2(node.left);
        if(node.val<=number)//如果root为最小值呢?
            return false;
        number=node.val;
        boolean flag2 = dg2(node.right);
        return flag1&&flag2;
    }

    public static void main(String[] args) {
        TreeNode nodeByArr = TreeNode.getNodeByArr(new Integer[]{5, 4, 6, null, null, 3, 7});
        No98验证二叉搜索树 n=new No98验证二叉搜索树();
        boolean validBST = n.isValidBST(nodeByArr);
        System.out.println(validBST);
    }

}
